﻿using System;
using System.Collections.Generic;
using System.Text;

namespace Graphs
{
    /// <summary>
    /// 使用一个 bool 数组来记录和起点连通地所有顶点。递归方法会标记给定地顶点并调用自己来访问该顶点地相邻顶点列表中
    /// 所有没有被标记过地顶点。 如果图是连通的，每个邻接链表中的元素都会被标记。
    /// </summary>
    public class DepthFirstSearch
    {
        private bool[] marked;
        private int count;

        public DepthFirstSearch(Graph G,int s)
        {
            marked = new bool[G.V()];
            Dfs(G,s);
        }

        private void Dfs(Graph g, int V)
        {
            marked[V] = true;
            count++;
            foreach (var w in g.Adj(V))
            {
                if (!marked[w])
                    Dfs(g,w);
            }
        }

        public bool Marked(int w)
        {
            return marked[w];
        }
    }
}
